from utils import *
import agents
import math, random, sys, time, bisect, string
from search import *

class HillNode(Node):
    def mutate(self, problem):
        return problem.mutate(self.state)

##
# deberia devolver el estado solamente; devuelve el par (estado, nodo)
# para que se pueda apreciar que el reultado del valor del nodo esta memoizado
#
# la memoizacion de los valores de los nodos carece de ventaja porque la frontera
# dura una iteracion del bucle while, y por lo tanto, se pierden
def sube_la_colina(problem, v=None):
    """From the initial node, keep choosing the neighbor with highest value,
    stopping when no neighbor is better. [Fig. 4.11]"""
    v = v or problem.value
    def value(n):
        return max(getattr(n, 'value', -infinity), v(n))
    value = memoize(value, 'value')
    current = HillNode(problem.initial)
    while True:
        frontera = current.mutate(problem)
        if not frontera:
            return current.state
        neighbor = argmax(frontera, value)
        if value(neighbor) <= value(current):
            return current.state, current
        current = neighbor

class SubQueens(NQueensProblem):
    def __init__(self, n, initial=None):
        NQueensProblem.__init__(self,n)
        self.initial = initial

    def mutate(self, state):
        r = []
        for c in range(self.N):
            s = state[:]
            s[c] = s[c] + 1
            if 0 <= s[c] < self.N: r.append(s)
            s = state[:]
            s[c] = s[c] - 1
            if 0 <= s[c] < self.N: r.append(s)
        return [ HillNode(x) for x in r ]

    def value(self, node):
        state = node.state
        cant = 0
        for c1 in range(self.N):
            c2 = c1 + 1
            while c2 < self.N:
                if self.conflict(state[c1], c1, state[c2], c2):
                    cant = cant + 1
                c2 = c2 + 1
        return -1 * cant

    def show(self, state):
        for r in range(self.N):
            for c in range(self.N):
                if state[c] == r:
                    print 'X',
                else: print '.',
            print
            

def nqueens_con_reinicio_aleatorio(N):
    cantidad_reinicios = 0
    while True:
        inicial = [ random.choice(range(N)) for x in range(N) ] 
        four = SubQueens(N, inicial)
        #print four.value(Node(four.initial))

        res, node = sube_la_colina(four)
        valor = four.value(node)
        print "este valor es el memoizado: %s" % (node.value,)
        print "valor=%3d, reinicios=%4d, estado=%s" % (valor, cantidad_reinicios, res)
        four.show(res)
        if valor == 0:
            break
        cantidad_reinicios = cantidad_reinicios + 1


nqueens_con_reinicio_aleatorio(8)
